package com.bascker.algorithm.practice.recursion.zero_sum_game.predict_the_winner;

public class Solution {

    // 1 <= nums.length <= 20
    // 0 <= nums[i] <= 10^7
    public boolean predictTheWinner(int[] nums) {
        // 玩家1作为先手, 按题意，若得分差值 >= 0 则玩家1获胜
        return diff(nums, 0, nums.length - 1, 1) >= 0;
    }

    /**
     * 计算先手和后手得分的差值
     * @param nums      数值数组
     * @param left      目前可选范围闭区间的左指针
     * @param right     目前可选范围闭区间的右指针
     * @param turn      先手 or 后手, 先手取值 1，后手取值 -1，以便控制得分的正负取值情况
     * @return          先后手得分差值
     */
    public int diff(int[] nums, int left, int right, int turn) {
        // 若区间只有一个值了，则当前玩家只用拿这个就行.
        if (left == right) {
            // 若玩家为后手，则取值为负数
            return nums[left] * turn;
        }

        // 玩家选择左区间场景下的取值
        int scoreLeft = nums[left] * turn + diff(nums, left + 1, right, -turn);
        // 玩家选择右区间场景下的取值
        int scoreRight = nums[right] * turn + diff(nums, left, right - 1, -turn);

        // 若当前玩家是先手，则选择差值最大的场景 => 这样能让后手的可选局面更差，也是让自己局面更好
        if (turn == 1) {
            return Math.max(scoreLeft, scoreRight);
        }
        // 若是后手，则选择差值最小的场景 => 这样能让先手的可选局面更差，也是让自己局面更好
        else {
            return Math.min(scoreLeft, scoreRight);
        }
    }

}
